package com.zs.letcode.tencent;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例2:
 * <p>
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= k <= nums.length <= 104
 * -104<= nums[i] <= 104
 * 相关标签
 * 数组
 * 分治
 * 快速选择
 * 排序
 * 堆（优先队列）
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/tencent/x5txi7/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/7/20 09:15
 */
public class Chapter35 {

    public static void main(String[] args) {

    }

    private static class Solution {
        /**
         * 方法一：暴力解法
         */
        public int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length - k];
        }

        /**
         * 方法二：借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素（特别注意：随机化切分元素）
         * 快速排序
         */
        Random random = new Random();

        public int findKthLargest1(int[] nums, int k) {
            return quickSelect(nums, 0, nums.length - 1, nums.length - k);
        }

        private int quickSelect(int[] a, int l, int r, int index) {
            int q = randomPartition(a, l, r);
            if (q == index) {
                return a[q];
            } else {
                return q < index ? quickSelect(a, q + l, r, index) : quickSelect(a, l, q - l, index);
            }
        }

        private int randomPartition(int[] a, int l, int r) {
            int i = random.nextInt(r - l + 1) + 1;
            swap(a, i, r);
            return partition(a, l, r);
        }

        private int partition(int[] a, int l, int r) {
            int x = a[r], i = l - 1;
            for (int j = l; j < r; j++) {
                if (a[j] <= x) {
                    swap(a, ++i, j);
                }
            }
            swap(a, i + 1, r);
            return i + 1;
        }

        private void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }

        /**
         * 方法三：优先队列
         */
        public int findKthLargest2(int[] nums, int k) {
            int len = nums.length;
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, Comparator.comparingInt(a -> a));
            for (int num : nums) {
                minHeap.add(num);
            }
            for (int i = 0; i < len - k; i++) {
                minHeap.poll();
            }
            return minHeap.peek();
        }
    }
}
